1. Field of the Invention
The invention relates to a method and system that can be used especially to estimate the unknown geometrical transformations that have occurred in data, for example in an image, or in an audio or video sequence.
It can be applied to correcting the distortions that have occurred in the transmission of images and/or to obtaining information on message-carrying watermarks.
The invention is used for example in watermarking. Indeed, a geometrical transformation in an image most usually makes the watermark illegible. In watermarking a reference pattern in the image it is thus possible to make an estimation, in a watermark reader for example, of the geometrical transformation that has occurred, and then to reverse it before decoding the message-carrying watermark.
2. Description of the Prior Art
Resistance to geometrical transformation is a crucial problem in watermarking. The detection of the watermark is often made impossible when the received message is distorted with respect to the original message.
Modifications of the geometry of the image indeed often occur during the distribution or exploitation of a work. This is the case especially with shearing or scaling which may be related with changes in format.
Analog/digital and digital/analog transformations may introduce a distortion in the image or they may introduce line “jitter” in a video sequence.
There are also highly effective, ill-intentioned attacks, such as the Stirmark attack described in 1988 by F. Petitcolas et al in “Attacks on copyright marking systems”, Proceedings of 2nd Information Hiding Workshop. This attack was designed to prevent the accurate detection of watermarks.
Different methods designed to counter the harmful effect of geometrical modifications have therefore been developed. They can be classified under five categories:
1) The Watermarking of a Reference Pattern Known at Transmission and at Reception
A simple method that uses a reference pattern is described in the patent FR 2.792.797. In this invention, a reference pattern known as a co-watermark is added to the image. At reception, the search for maximum self-correlation between the received image and the reference pattern makes it possible to determine the original coordinates of the initial image. This method is resistant to shifting, shearing and translation undergone by the image, i.e. to the global distortions of the image. The method becomes inefficient when the geometrical transformation is more complicated, for example when the transformation is a rotation, a scaling or zooming, a carpet distortion, etc.
S. Pereira and T. Pun in “Fast Robust template Matching for Affine Resistant Image Watermarking”, Proceedings of International Workshop on Information, have proposed a more general co-watermarking method to resist affine transformations of the image. However, this method is limited and can be used to readjust the image only for affine geometrical transformations.
Another method proposed by S. Voloshynovskiy, F. Deguillaume, T. Pun in “Multibit Digital Watermarking Robust Against Non-linear Geometrical Transformations”, Proceedings of ICIP 01, is used to resist more complex global and/or local transformation. A reference pattern is watermarked orthogonally to the message which, for its part, consists of a symmetrical and periodic pattern. The decoding of the watermark and the estimation of the transformation are done in conjunction.
Two watermarks are inserted: the message-carrying watermark w1 and a reference watermark w2 (co-watermark). The message-carrying watermark consists of a block sized Kx, Ky symmetrized and periodized so as to obtain a block having the size of the image. The estimation is made in the Fourier domain: the fact that w1 is periodic implies the presence of the evenly spaced out peaks in the Fourier domain. For each block of the image, it is considered that the local distortion may be approximated by an affine geometrical transformation (a combination of rotation, non-uniform scaling and translation). During decoding, for each block, a search is made for the affine transformation that minimizes the distance between the reference watermark and the distorted image, provided that this transformation is plausible (for example cases of excessive stretching are eliminated). This method is efficient for readjusting the watermarks but is complex because it calls for an exhaustive search for parameters for each block of the image. Furthermore, it is based on an approximation (a non-linear local transformation cannot be reduced to a succession of affine transformations) and does not take account of the correlations existing between estimated parameters for neighboring blocks.
2) Watermarking in an Invariant Space by Geometrical Transformation
O'Ruanaidh and T. Pun in “Rotation, scale and translation invariant spread spectrum digital image watermarking”, Signal Processing, Vol. 66 No. 3, p 303–317, propose that the watermarking should be performed in an invariant space by rotation, translation, scaling, to overcome the effects of any geometrical transformation that may be performed on the image. This result is obtained by taking advantage of the properties of the Fourier-Mellin transform. The advantage of this method is that it enables resistance to geometrical transformations without the need for any preliminary synchronization. Its drawback is that the invariant properties are no longer respected when the circular translation is replaced by a shearing of the image. Furthermore, this method is complex and costly in terms of computation and may raise problems of digital computation. Again, the density of the information embedded in the image varies greatly
3) Watermarking in a Referential System Related to the Image
In another approach, a reference system linked to the image is chosen in order to embed the watermark and detect it. When the geometry of the image is distorted, the referential system will be modified in the same way, and it will then be possible to recover the mark without any need for an external synchronization.
The method described by P. Bas, J. M Chassery and B. Macq, “Robust Watermarking based on the warping of predefined triangular patterns” Proceedings of SPIE—January 2000, uses a local system of reference coordinates linked to a set of regions characteristic of the image. These regions may be defined in particular by points of interest, such as those obtained by a Harris detector described in C. Harris and M. Stephen, “A combined corner and edge detector”, 4 Alvey Vision Conf, p.147–151,1988.
4) The Redundant Insertion of Watermarking in the Image.
5) The Exhaustive Search for All the Possible Transformations.
The idea of the invention consists especially in estimating local distortions or distortions considered to be local, introduced into the data, such as images, audio, video etc., where the estimation may be done globally or locally.